package com.shujia.java.day4;

public class Demo8Find {
    public static void main(String[] args) {


        int[] nums = {1, 2, 3, 4, 5, 7, 8, 12, 23, 45, 77};
        int num = 3;
        int index = getIndex(nums, num);
        System.out.println(index);

        //调用二分查找方法
        int i = branIndex(nums, num);
        System.out.println(i);

    }

    /**
     * 普通查找
     * 时间复杂度 O(n)
     */

    static int getIndex(int[] nums, int num) {
        for (int i = 0; i <= nums.length; i++) {
            if (num == nums[i]) {
                return i;
            }
        }

        return -1;
    }

    /**
     * 二分查找
     * 时间复杂度  O(log2n)
     * 前提条件：数组必须有序
     * 1、确定中间元素
     * 如果目标值大于中间元素，说明目标值在右边，
     * 下一次只需要取右边的元素进行比较
     * 重复上面的过程
     */

    static int branIndex(int[] nums, int num) {

        //查找范围
        int start = 0;
        int end = nums.length - 1;

        while (start <= end) {

            //计算中心位置
            //int mid = (start + end) / 2;
            int mid = (start + end) >> 1;//效率比上面高

            if (num > nums[mid]) {//目标值在数组的右边
                //将查找范围缩小
                start = mid + 1;
            } else if (num < nums[mid]) {//目标值在数组的左边
                end = mid - 1;
            } else {
                //找到结果,返回下标
                return mid;
            }
        }

        return -1;//如果不存在返回-1

    }


}
